package LeetCodeTask.BinarySearch;

/**
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 *
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
 * 输出：true
 *
 * 相信大部分人看到题目马上就有思路，列升序+行升序的二维数组查找问题，
 * 两步走：1、通过首列查找target所在行；2、查找该行。而最有效率的查找算法莫过于二分查找
 */
public class SearchMatrix {

    public boolean searchMatrix(int[][] matrix, int target) {

        int m = matrix.length;
        if(m==0)
            return  false;
        int n = matrix[0].length;
        int left = 0;
        int right = m*n-1;
        int pivotIdx, pivotElement;

        while (left<=right){
            pivotIdx = (left+right)/2;
            pivotElement = matrix[pivotIdx/n][pivotIdx%n];
            if(target==pivotElement){
                return true;
            }else if(target>pivotElement){
                left=pivotIdx+1;
            }else{
                right=pivotIdx-1;
            }
        }
        return false;

    }

}
